package com.leetcode;

/**
 * @Author: chenyuan.wang
 * @Description: TODO 最长回文子串
 * @Date: 2019/4/26 14:23
 * @Version 1.0
 */
public class LongestPalindromicSubstring {
    /**
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * <p>
     * 示例 1：
     * <p>
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     * <p>
     * 输入: "cbbd"
     * 输出: "bb"
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s.length()<=1) {
            return s;
        }
        String longest = s.charAt(0)+"";
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        for(int j = length-1;j>=0;j--){
            //j在前,i在后
            for(int i = j;i<length;i++){
                dp[j][i] = s.charAt(i)==s.charAt(j)&&((i-j<3)||dp[j+1][i-1]);
                if(dp[j][i]&&i-j+1>longest.length()){
                    longest = s.substring(j,i+1);
                }
            }
        }
        return longest;

    }

    public static void main(String[] args) {
        String babad = longestPalindrome("babad");
        String cbbd = longestPalindrome("\"esbtzjaaijqkgmtaajpsdfiqtvxsgfvijpxrvxgfumsuprzlyvhclgkhccmcnquukivlpnjlfteljvykbddtrpmxzcrdqinsnlsteonhcegtkoszzonkwjevlasgjlcquzuhdmmkhfniozhuphcfkeobturbuoefhmtgcvhlsezvkpgfebbdbhiuwdcftenihseorykdguoqotqyscwymtjejpdzqepjkadtftzwebxwyuqwyeegwxhroaaymusddwnjkvsvrwwsmolmidoybsotaqufhepinkkxicvzrgbgsarmizugbvtzfxghkhthzpuetufqvigmyhmlsgfaaqmmlblxbqxpluhaawqkdluwfirfngbhdkjjyfsxglsnakskcbsyafqpwmwmoxjwlhjduayqyzmpkmrjhbqyhongfdxmuwaqgjkcpatgbrqdllbzodnrifvhcfvgbixbwywanivsdjnbrgskyifgvksadvgzzzuogzcukskjxbohofdimkmyqypyuexypwnjlrfpbtkqyngvxjcwvngmilgwbpcsseoywetatfjijsbcekaixvqreelnlmdonknmxerjjhvmqiztsgjkijjtcyetuygqgsikxctvpxrqtuhxreidhwcklkkjayvqdzqqapgdqaapefzjfngdvjsiiivnkfimqkkucltgavwlakcfyhnpgmqxgfyjziliyqhugphhjtlllgtlcsibfdktzhcfuallqlonbsgyyvvyarvaxmchtyrtkgekkmhejwvsuumhcfcyncgeqtltfmhtlsfswaqpmwpjwgvksvazhwyrzwhyjjdbphhjcmurdcgtbvpkhbkpirhysrpcrntetacyfvgjivhaxgpqhbjahruuejdmaghoaquhiafjqaionbrjbjksxaezosxqmncejjptcksnoq\"");
        System.out.println(babad);
        System.out.println(cbbd);
    }
}
